package com.leetcode.algorithm.y22.m07;

/**
 * 1855. 下标对中的最大距离
 * 
 * https://leetcode.cn/problems/maximum-distance-between-a-pair-of-values/
 * 
 * @author jie.deng
 *
 */
class Question1855Solution01 {

	public int maxDistance(int[] nums1, int[] nums2) {
		int maxDistance = 0;
		for (int i = 0; i < nums1.length; i++) {
			int idx = searchIdx(nums2, i + maxDistance + 1, nums1[i]);
			if (idx != -1) {
				maxDistance = idx - i;
			}
		}
		return maxDistance;
	}

	private int searchIdx(int[] nums, int left, int num) {
		int right = nums.length - 1;
		if (left > right || nums[left] < num) {
			return -1;
		}
		while (left < right) {
			int mid = left + ((right - left + 1) >> 1);
			if (nums[mid] >= num) {
				left = mid;
			} else {
				right = mid - 1;
			}
		}
		return left;
	}

}